home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / genra_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  10.3 KB  |  383 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  genra_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_GENRA_TREE_H
  17. #define LEDA_GENRA_TREE_H
  18.  
  19. // macros for counting 
  20. //
  21. #ifdef COUNT
  22. #define COUNT_SEC(l)    genra_tree::sec_op[last_op]+=l;
  23. #define COUNT_INS     genra_tree::prim_op[0]++; genra_tree::last_op=0;
  24. #define COUNT_DEL    genra_tree::prim_op[1]++; genra_tree::last_op=1;
  25. #define COUNT_VARS    static int prim_op[2],sec_op[2],last_op;
  26. #define COUNT_FUNC    float analyze_del(); float analyze_ins();\
  27.             void reset();
  28. #else
  29. #define COUNT_SEC(l)
  30. #define COUNT_INS
  31. #define COUNT_DEL
  32. #define COUNT_VARS
  33. #define COUNT_FUNC    void analyze() {} ;  void reset() {} ;
  34. #endif
  35.  
  36.  
  37.  
  38. #include <LEDA/list.h>
  39.  
  40. //
  41. // D-Dimensional Generic Range Trees
  42. // ---------------------------------
  43. //
  44. //
  45. // exchangable underlying data structure
  46. //
  47. // 7/92, M.Paul
  48. //
  49.  
  50.  
  51.  
  52. // an element of a genra_tree stores key and inf
  53. //
  54. class grt_inf
  55. {
  56.   friend class genra_tree ;
  57.  
  58.   GenPtr* g_key ;
  59.   GenPtr g_inf ;
  60.  
  61.   public:
  62.  
  63.     LEDA_MEMORY( grt_inf ) ;            // better proteced
  64.  
  65.     grt_inf( GenPtr k[], GenPtr i ) { g_key=k; g_inf=i; }
  66.  
  67.     GenPtr*& key() { return g_key; } ;
  68.     GenPtr key( int d ) { return g_key[d]; } ;
  69.     GenPtr& inf() { return g_inf; } ;
  70. } ;
  71.  
  72. typedef grt_inf* grt_item ;
  73.  
  74.  
  75.  
  76. #include <LEDA/impl/rs_tree.h>            // include default UDS
  77. typedef rs_tree def_uds ;
  78.  
  79.  
  80.  
  81. // genra_tree is a generic d-dimensional range tree with default
  82. // underlying data structure def_uds
  83. //
  84. class genra_tree : public def_uds
  85. {
  86.   COUNT_VARS
  87.   static grt_item GI_L, GI_H ;    
  88.  
  89.   // functions used from underlying data structure are virtual
  90.  
  91.   virtual GenPtr r_clear() { return def_uds::r_clear(); } ;
  92.   virtual int r_size() const { return def_uds::r_size(); } ;
  93.   virtual GenPtr r_first_item() const 
  94.     { return def_uds::r_first_item(); } ;
  95.   virtual GenPtr r_next_item( GenPtr p ) const 
  96.     { return def_uds::r_next_item(p); } ;
  97.   virtual GenPtr r_inf( GenPtr p ) const { return def_uds::r_inf(p); } ;
  98.   virtual void r_partition( GenPtr low, GenPtr high, 
  99.                 list<GenPtr>& node_infs, list<GenPtr>& leaf_infs ) const 
  100.     { def_uds::r_partition(low,high,node_infs,leaf_infs); } ;
  101.   virtual void r_query( GenPtr low, GenPtr high, list<GenPtr>& infs ) const
  102.     { def_uds::r_query(low,high,infs); } ;
  103.   virtual void r_leaf_infs( GenPtr p, list<GenPtr>& infs ) const
  104.     { def_uds::r_leaf_infs(p,infs); } ;
  105.   virtual list<GenPtr> r_all_leaf_infs() const
  106.     { return def_uds::r_all_leaf_infs(); } ;
  107.   virtual void r_insert( GenPtr key, GenPtr leaf_inf, GenPtr inner_inf,
  108.                 list<GenPtr>& cn, list<GenPtr>& in )
  109.     { def_uds::r_insert(key,leaf_inf,inner_inf,cn,in); } ;
  110.   virtual GenPtr r_delete( GenPtr key, list<GenPtr>& cn, list<GenPtr>& dn )
  111.     { return def_uds::r_delete(key,cn,dn); } ;
  112.  
  113.   protected:
  114.  
  115.     LEDA_MEMORY( genra_tree ) ;
  116.  
  117.     int dim1 ;            // one less than the dimension of tree
  118.  
  119.     virtual genra_tree* create_genra_tree( int d )
  120.       { return new genra_tree(d); } ;
  121.  
  122.     // virtual functions of uds
  123.  
  124.     void print_key( GenPtr ) const ;
  125.     void print_inf( GenPtr ) const ;
  126.     int cmp( GenPtr, GenPtr ) const ;
  127.     void clear_key(GenPtr&) const {}
  128.     void clear_inf(GenPtr&) const {}
  129.     void copy_key(GenPtr&) const {}
  130.     void copy_inf(GenPtr&) const {}
  131.     int int_type() const { return 0; }
  132.  
  133.     // user defined virtual functions of class genra_tree
  134.  
  135.     virtual int r_cmp( GenPtr x, GenPtr y ) const
  136.       { return compare(x,y); } ;
  137.     virtual void r_copy_key( GenPtr*& ) const {}
  138.     virtual void r_copy_inf( GenPtr& ) const {} 
  139.     virtual void r_clear_key( GenPtr*& ) const {}
  140.     virtual void r_clear_inf( GenPtr& ) const {}
  141.  
  142.     int is_between( grt_item k_gi, grt_item l_gi, grt_item h_gi ) const;
  143.     void query( grt_item l_gi, grt_item h_gi, list<GenPtr>& lgi ) const ;
  144.     void insert_item( grt_item gi ) ;
  145.     void del_item( grt_item gi ) ;
  146.     void build_tree( list<GenPtr>& lgi ) ;
  147.  
  148.   public:
  149.  
  150.     virtual void r_print_key( GenPtr* x ) const 
  151.       { for( int d=dim1; d>=0; d-- ) cout << x[d] << " "; }
  152.     virtual void r_print_inf( GenPtr i ) const { cout << i << " "; }
  153.     
  154.     virtual void print_tree(){ def_uds::print_tree(); } ;
  155.     void print() ;
  156.     void test() ;
  157.  
  158.     genra_tree( int d = 2 ) { dim1 = d-1; }
  159.  
  160.     void clear() ;
  161.     virtual ~genra_tree() { clear(); }
  162.  
  163.     int dimension() const { return dim1+1; }
  164.     int size() const { return r_size(); }
  165.     int empty() const { return r_size()==0; }
  166.     void query( GenPtr low[], GenPtr high[], list<GenPtr>& lgi ) const ;
  167.     grt_item lookup( GenPtr key[] ) const ;
  168.     list<GenPtr> all_items() const ;
  169.  
  170.     grt_item insert( GenPtr key[], GenPtr inf ) ;
  171.     void del( GenPtr key[] ) ;
  172.  
  173.     COUNT_FUNC
  174. } ;
  175.  
  176. typedef genra_tree* grt_p ;
  177.  
  178.  
  179.  
  180. //
  181. // some inline functions of class genra_tree
  182. //
  183.  
  184. // returns a list of all grt_items with key between low[] and high[]
  185. //
  186. inline void genra_tree::query( GenPtr low[], GenPtr high[],
  187.                    list<GenPtr>& lgi ) const 
  188. {
  189.   lgi.clear() ;
  190.  
  191.   if( ! empty() ) {
  192.     GI_L->key() = low ;  GI_H->key() = high ;
  193.     query( GI_L, GI_H, lgi ) ;
  194.   }
  195. }
  196.  
  197.  
  198.  
  199. // returns a list of all grt_items
  200. //
  201. inline list<GenPtr> genra_tree::all_items() const 
  202. {
  203.   return r_all_leaf_infs() ;
  204. }
  205.  
  206.  
  207.  
  208. // insert inf with key[] or change inf, if key[] exists
  209. //
  210. inline grt_item genra_tree::insert( GenPtr key[], GenPtr inf ) 
  211. {
  212.   grt_item gi = lookup( key ) ;            // search for key[]
  213.   
  214.   if( ! gi ) {                    // insert new item
  215.     gi = new grt_inf( key, inf ) ;  
  216.     r_copy_inf( gi->inf() ) ;  r_copy_key( gi->key() ) ;  
  217.     COUNT_INS
  218.     insert_item( gi ) ;                
  219.   }
  220.   else {                    // change inf
  221.     // r_clear_inf( gi->inf() ) ;
  222.     // gi->inf() = inf ;  
  223.     // r_copy_inf( gi->inf() ) ;
  224.   }
  225.  
  226.   return gi ;
  227. } ;
  228.  
  229.  
  230.  
  231. // delete inf with key[]
  232. //
  233. inline void genra_tree::del( GenPtr key[] )
  234. {
  235.   grt_item gi = lookup( key ) ;                 // search for key[]
  236.  
  237.   if( gi ) {
  238.     COUNT_DEL
  239.     del_item( gi ) ;
  240.     r_clear_inf( gi->inf() ) ;  r_clear_key( gi->key() ) ;  
  241.     delete gi ;
  242.   }
  243. } ;
  244.  
  245.  
  246.  
  247. // checks if k_gi[] lies between l_gi[] and h_gi[] for all dims < dim1
  248. //
  249. inline int genra_tree::is_between( grt_item k_gi, 
  250.                               grt_item l_gi, grt_item h_gi ) const
  251. {
  252.   register int d = dim1 ;
  253.  
  254.   while( --d >= 0 ) 
  255.     if( r_cmp(k_gi->key(d),l_gi->key(d)) < 0 || 
  256.     r_cmp(k_gi->key(d),h_gi->key(d)) > 0 ) 
  257.       break ;
  258.  
  259.   return d<0 ? 1 : 0 ;
  260. }
  261.  
  262.  
  263.  
  264. //
  265. // virtual functions for uds
  266. //
  267.  
  268. inline void genra_tree::print_key( GenPtr x ) const
  269. { r_print_key( grt_item(x)->key() ) ;
  270. }
  271.  
  272. inline void genra_tree::print_inf( GenPtr x ) const
  273. { r_print_inf( grt_item(x)->inf() ) ;
  274. }
  275.  
  276. // use key in dim1 first, then take inf
  277. //
  278. inline int genra_tree::cmp( GenPtr x, GenPtr y ) const
  279. {
  280.   int c = r_cmp( grt_item(x)->key(dim1), grt_item(y)->key(dim1) ) ;
  281.   return c ? c : compare( (GenPtr) grt_item(x)->inf(), 
  282.               (GenPtr) grt_item(y)->inf() ) ;
  283. }
  284.  
  285.  
  286.  
  287. //
  288. // add capability of exchangable underlying data structure
  289. //
  290.  
  291. #define GENRA_TREE(a)    name2(a,_GENRA_TREE)
  292.  
  293.  
  294.  
  295. #define GENRA_TREE_DECL(impl)\
  296. \
  297. class GENRA_TREE(impl) : public genra_tree, public impl\
  298. {\
  299. \
  300.   GenPtr r_clear() { return impl::r_clear(); }\
  301.   int r_size() const { return impl::r_size(); }\
  302.   GenPtr r_first_item() const { return impl::r_first_item(); }\
  303.   GenPtr r_next_item( GenPtr p ) const \
  304.     { return impl::r_next_item(p); }\
  305.   GenPtr r_inf( GenPtr p ) const { return impl::r_inf(p); }\
  306.   void r_partition( GenPtr low, GenPtr high,\
  307.             list<GenPtr>& node_infs, list<GenPtr>& leaf_infs ) const \
  308.     { impl::r_partition(low,high,node_infs,leaf_infs); }\
  309.   void r_query( GenPtr low, GenPtr high, list<GenPtr>& infs ) const\
  310.     { impl::r_query(low,high,infs); }\
  311.   void r_leaf_infs( GenPtr p, list<GenPtr>& infs ) const\
  312.     { impl::r_leaf_infs(p,infs); }\
  313.   list<GenPtr> r_all_leaf_infs() const\
  314.     { return impl::r_all_leaf_infs(); }\
  315.   void r_insert( GenPtr key, GenPtr leaf_inf, GenPtr inner_inf,\
  316.          list<GenPtr>& cn, list<GenPtr>& in )\
  317.     { impl::r_insert(key,leaf_inf,inner_inf,cn,in); }\
  318.   GenPtr r_delete( GenPtr key, list<GenPtr>& cn, list<GenPtr>& dn )\
  319.     { return impl::r_delete(key,cn,dn); }\
  320. \
  321.   protected:\
  322. \
  323.     LEDA_MEMORY( GENRA_TREE(impl) ) ;\
  324. \
  325.     genra_tree* create_genra_tree( int d )\
  326.       { return new GENRA_TREE(impl)(d); } ;\
  327. \
  328.     void print_key( GenPtr x ) const { genra_tree::print_key(x); }\
  329.     void print_inf( GenPtr x ) const  { genra_tree::print_inf(x); }\
  330.     int cmp( GenPtr x, GenPtr y ) const\
  331.       { return genra_tree::cmp(x,y); }\
  332.     void clear_key(GenPtr&) const {}\
  333.     void clear_inf(GenPtr&) const {}\
  334.     void copy_key(GenPtr&) const {}\
  335.     void copy_inf(GenPtr&) const {}\
  336.     int int_type() const { return 0 ; }\
  337. \
  338.     int r_cmp( GenPtr x, GenPtr y ) const { return compare(x,y); }\
  339.     void r_copy_key( GenPtr*& ) const {}\
  340.     void r_copy_inf( GenPtr& ) const {}\
  341.     void r_clear_key( GenPtr*& ) const {}\
  342.     void r_clear_inf( GenPtr& ) const {}\
  343. \
  344.     void query( grt_item l_gi, grt_item h_gi, list<GenPtr>& lgi ) const \
  345.       { genra_tree::query(l_gi,h_gi,lgi); }\
  346.     int is_between( grt_item k_gi, grt_item l_gi, grt_item h_gi ) const\
  347.       { return genra_tree::is_between(k_gi,l_gi,h_gi); }\
  348.     void insert_item( grt_item gi ){ genra_tree::insert_item(gi); }\
  349.     void del_item( grt_item gi ){ genra_tree::del_item(gi); }\
  350.     void build_tree( list<GenPtr>& lgi ) { genra_tree::build_tree(lgi); }\
  351. \
  352.   public:\
  353. \
  354.     virtual void r_print_key( GenPtr* x ) const\
  355.       { for( int d=dim1; d>=0; d-- ) cout << x[d] << " "; }\
  356.     virtual void r_print_inf( GenPtr i ) const { cout << i << " "; }\
  357. \
  358.     void print_tree(){ impl::print_tree(); } ;\
  359.     void print(){ genra_tree::print(); } ;\
  360. \
  361.     GENRA_TREE(impl)( int d = 2 ) { dim1 = d-1; }\
  362.     virtual ~GENRA_TREE(impl)() { clear(); }\
  363. \
  364.     void clear() { genra_tree::clear(); }\
  365.     int dimension() const { return genra_tree::dimension(); }\
  366.     int size() const { return genra_tree::size(); }\
  367.     int empty() const { return genra_tree::empty(); }\
  368.     void query( GenPtr low[], GenPtr high[], list<GenPtr>& lgi ) const\
  369.       { genra_tree::query(low,high,lgi); }\
  370.     grt_item lookup( GenPtr key[] ) const\
  371.       { return genra_tree::lookup(key); }\
  372.     list<GenPtr> all_items() const { return genra_tree::all_items(); }\
  373. \
  374.     grt_item insert( GenPtr key[], GenPtr inf )\
  375.       { return genra_tree::insert(key,inf); }\
  376.     void del( GenPtr key[] ) { genra_tree::del(key); }\
  377. \
  378. } ;\
  379.  
  380.  
  381.  
  382. #endif
  383.